#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef __int128 LL;
const int IN=1e7,OUT=2e7;
char _i[IN],*_I=_i,_o[OUT],*_O=_o,__[50];
inline ll rd(){
	for(;*_I<0x30;_I++);ll x=0;
	for(;*_I>0x2f;_I++)x=(x<<1)+(x<<3)+(*_I^0x30);
	return x;
}
inline void wr(LL x){
	int l=0;do __[l++]=0x30|x%10;while(x/=10);
	while(l--)*_O++=__[l];*_O++=0xa;
}
namespace MAOJUN{

const int N=4e5+5;
int n;

namespace SUB3{
	set<ll>vs;ll f[N],g[N];
	inline void slv(){
		for(ll v;n--;){
			v=rd();
			if(vs.find(v)==vs.end())vs.insert(v);
			else vs.erase(vs.find(v));
			int m=0;
			for(ll x:vs){m++;f[m]=g[m]=x;}
			for(int i=1;i<=m;i++)f[i]+=f[i-1];
			reverse(g+1,g+m+1);
			for(int i=1;i<=m;i++)g[i]+=g[i-1];
			ll rs=0;
			for(int i=1;i<m;i++)rs+=min(f[i+1],g[i])-f[i];
			wr(rs);
		}
	}
}
mt19937 rnd(350297);
int idx=0,rt=0,ls[N],rs[N],ky[N],sz[N];ll vl[N],s1[N];LL s2[N];
inline void pu(int p){
	sz[p]=sz[ls[p]]+sz[rs[p]]+1;
	s1[p]=s1[ls[p]]+s1[rs[p]]+vl[p];
	s2[p]=s2[ls[p]]+s2[rs[p]]+(LL)(vl[p]+s1[rs[p]])*(sz[ls[p]]+1);
}
void spl1(int p,int k,int&L,int&R){
	if(!p){L=R=0;return;}
	if(k<=sz[ls[p]]){R=p;spl1(ls[p],k,L,ls[p]);pu(p);}
	else{L=p;spl1(rs[p],k-sz[ls[p]]-1,rs[p],R);pu(p);}
}
void spl2(int p,ll k,int&L,int&R){
	if(!p){L=R=0;return;}
	if(k<=vl[p]){R=p;spl2(ls[p],k,L,ls[p]);pu(p);}
	else{L=p;spl2(rs[p],k,rs[p],R);pu(p);}
}
int mrg(int x,int y){
	if(!x||!y)return x|y;
	if(ky[x]<ky[y]){rs[x]=mrg(rs[x],y);pu(x);return x;}
	else{ls[y]=mrg(x,ls[y]);pu(y);return y;}
}
set<ll>vs;
namespace SUB1{
	inline void slv(){
		int x,y,z;
		for(ll v;n--;){
			v=rd();
			if(vs.find(v)==vs.end()){
				vs.insert(v);
				z=++idx;sz[z]=1;vl[z]=s1[z]=s2[z]=v;ky[z]=rnd();
				spl2(rt,v,x,y);rt=mrg(x,mrg(z,y));
			}else{
				vs.erase(vs.find(v));
				spl2(rt,v,x,y);spl1(y,1,z,y);rt=mrg(x,y);
			}
			if(vs.size()<2){wr(0);continue;}
			int m=sz[rt],l=1,r=m,md;
			while(l<r){
				md=l+r>>1;
				ll S=0;
				for(int p=rt,k=md+1;k;){
					if(k==sz[p]){S+=s1[p];break;}
					if(k<=sz[ls[p]])p=ls[p];
					else{S+=s1[ls[p]]+vl[p];k-=sz[ls[p]]+1;p=rs[p];}
				}
				for(int p=rt,k=md;k;){
					if(k==sz[p]){S-=s1[p];break;}
					if(k<=sz[rs[p]])p=rs[p];
					else{S-=s1[rs[p]]+vl[p];if(S<=0)break;k-=sz[rs[p]]+1;p=ls[p];}
				}
				S<=0?l=md+1:r=md;
			}
			int p=l;
			LL as=(p-m)*s1[rt]-*vs.begin();
			spl1(rt,m-p+1,x,y);as+=s2[x]+(m-p+1)*s1[y];rt=mrg(x,y);
			spl1(rt,p,x,y);as+=s2[y]-s1[y];rt=mrg(x,y);
			wr(as);
		}
	}
}
namespace SUB2{
	int x,y,z,m=0;
	inline bool chk(int md){
		ll S=0;
		for(int p=rt,k=md+1;k;){
			if(k==sz[p]){S+=s1[p];break;}
			if(k<=sz[ls[p]])p=ls[p];
			else{S+=s1[ls[p]]+vl[p];k-=sz[ls[p]]+1;p=rs[p];}
		}
		for(int p=rt,k=md;k;){
			if(k==sz[p])return S<=s1[p];
			if(k<=sz[rs[p]])p=rs[p];
			else{if((S-=s1[rs[p]]+vl[p])<=0)return 1;k-=sz[rs[p]]+1;p=ls[p];}
		}
		return 0;
	}
	inline void slv(){
		int p=1;
		for(ll v;n--;){
			v=rd();
			if(vs.find(v)==vs.end()){
				vs.insert(v);m++;
				z=++idx;sz[z]=1;vl[z]=s1[z]=s2[z]=v;ky[z]=rnd();
				spl2(rt,v,x,y);rt=mrg(x,mrg(z,y));
			}else{
				vs.erase(vs.find(v));m--;
				spl2(rt,v,x,y);spl1(y,1,z,y);rt=mrg(x,y);
			}
			if(vs.size()<2){wr(0);continue;}
			int l=1,r=m,md;
			if(p<m&&chk(p))for(p++;p<m&&chk(p);p++);
			else for(;p>1&&chk(p-1);p--);
			LL as=(p-m)*s1[rt]-*vs.begin();
			spl1(rt,m-p+1,x,y);as+=s2[x]+(m-p+1)*s1[y];rt=mrg(x,y);
			spl1(rt,p,x,y);as+=s2[y]-s1[y];rt=mrg(x,y);
			wr(as);
		}
	}
}
inline void main(){
	n=rd();
	if(n<=1000)SUB3::slv();
	else if(n<=3e4)SUB1::slv();
	else SUB2::slv();
}

}int main(){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	fread(_i,1,IN,stdin);
	MAOJUN::main();
	fwrite(_o,1,_O-_o,stdout);
	return 0;
}